/**
 * Consider the fraction, p/q, where p and q are positive integers. If p < q 
 * and gcd(p,q)=1, it is called a reduced proper fraction.
 *
 * If we list the set of reduced proper fractions for q <= 8 in ascending order
 * of value, we get:
 *
 *   1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 
 *   5/7, 3/4, 4/5, 5/6, 6/7, 7/8
 *
 * It can be seen that there are 3 fractions between 1/3 and 1/2.
 * 
 * How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper 
 * fractions for q <= 12,000?
 *
 * ANSWER: 7295372.
 */

#include <iostream>
#include <iterator>
#include "gcd.h"
#include "prime.h"
#include "farey.h"

void solve_problem_73()
{
	const int M = 12000;
	const int a = 3, b = 2;

	long long count = 0;
#if 1
	farey_sequence<int> f(M);
	farey_sequence<int>::iterator it1 = f.find(1, a), it2 = f.find(1, b);
	count = std::distance(it1, it2) - 1;
#elif 1
	for (int q = 2; q <= M; q++)
	{
		for (int p = q/a+1; p <= (q-1)/b; p++)
		{
			if (greatest_common_divisor(p, q) == 1)
				++count;
		}
	}
#else
	generate_coprime_pairs([=,&count](int q, int p) -> bool {
		if (q > M)
			return false;
		if (a*p > q && b*p < q)
			++count;
		return true;
	});
#endif
	std::cout << count << std::endl;
}
